home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / GRAPHICS / ROTATE.ZIP / ROTATE.TXT
Encoding:
Text File  |  1997-01-09  |  3.7 KB  |  96 lines
  1.                     A Fast Algorithm for Rotating Bitmaps
  2.  
  3.                                       by
  4.                                   Karl Lager
  5.  
  6.   According to "Tricks of the Game Programming Gurus", rotating
  7. a bitmap in real time generally isn't done because of the complex
  8. math involved and slow speed. However, with a few optimizations 
  9. it can be done nearly as fast as bitmap scaling.
  10.  
  11.   To start with, each pixel can be given x,y coordinates.  To rotate 
  12. these by an angle t about the 0 axis , the new coordinates can be 
  13. plotted as (x',y') = (x cos(t) - y sin(t),  y cos(t) + x sin(t)).
  14. ( for x = right, y = down, clockwise rotations. )
  15.  
  16. To convert a pixel on screen to the bitmap, the directions would be 
  17. reversed:
  18.         
  19.         (x',y') = (x cos(t) + y sin(t), y cos(t) - x sin(t);
  20.  
  21. To rotate a whole bitmap, you can plot
  22.         
  23.         ( for y = min_y to max_y
  24.             for x = min_x to max_x
  25.                x' = (x cos (t) + y sin(t))
  26.                y' = (y cos(t) - x cos(t))
  27.                if (x', y') is in the bounds of the bitmap, 
  28.                  get pixel(x',y') and plot the pixel to (x,y) on screen.
  29.         )
  30.  
  31. Now, you might want to rotate the bitmap about an arbitrary pixel(x1',y1'), 
  32. and put it to an arbitrary point on screen(x1,y1), and to do this you 
  33. could get pixel(x'+ x1', y'+ y1') and put it to (x + x1, y + y1) on screen.
  34.  
  35. To speed this procedure up, you can start by taking the trig equations
  36. out of the inner loop.  The angle doesn't change, so these calculations
  37. should only be done once.
  38.  
  39.         double cosT,sinT;
  40.         cosT = cos(t);
  41.         sinT = sin(t);
  42.         for (y = min_y - y1; y <= max_y - y1; y++)
  43.           for (x = min_x - x1; x <= max_x - x1; x++)
  44.            { x' = (x * cosT + y * sinT);
  45.              y' = (y * cosT - x * sinT);
  46.              if (x'+ x1', y'+ y1') is in the bounds of the bitmap, 
  47.                get pixel(x'+ x1', y'+ y1') and plot the pixel to 
  48.                (x + x1, y + y1) on screen.
  49.            }
  50.  
  51.  
  52.  
  53. Since x and y are incremented by a constant value, the code can be 
  54. streamlined further by removing the multiplications from the inner loop:
  55.  
  56.         double cosT,sinT;
  57.         cosT = cos(t);
  58.         sinT = sin(t);
  59.         for (y = min_y - y1; y <= max_y - y1; y++)
  60.          { x' = (min_x-x1) * cosT + y * sinT;
  61.            y' = y * cosT - (min_x-x1) * sinT;
  62.            for (x = min_x-x1; x <= max_x - x1; x++)
  63.             { if (x'+ x1', y'+ y1') is in the bounds of the bitmap, 
  64.                  get pixel(x'+ x1',y'+ y1') and plot the pixel to 
  65.                  (x + x1,y + y1) on screen.
  66.               x' += cosT;
  67.               y' -= sinT;
  68.             }
  69.          }
  70.  
  71. Finally, remove the extra additions from the inner loops:
  72.  
  73.         double cosT,sinT;
  74.         cosT = cos(t);
  75.         sinT = sin(t);
  76.         for (y = min_y; y <= max_y; y++)
  77.          { x' = (min_x-x1) * cosT + (y-y1) * sinT + x1';
  78.            y' = (y-y1) * cosT - (min_x-x1) * sinT + y1';
  79.            for (x = min_x; x <= max_x; x++)
  80.             { if (x', y') is in the bounds of the bitmap, 
  81.                  get pixel(x', y') and plot the pixel to 
  82.                  (x, y) on screen.
  83.               x' += cosT;
  84.               y' -= sinT;
  85.             }
  86.          }
  87.  
  88.   Thus you have gone from doing 4 transcendental functions (or 4 lookups
  89. and 4 multiplications if you are using lookup tables) per pixel to
  90. doing 2 additions per pixel. That's going from instructions that take
  91. a couple hundred CPU cycles with a coprocessor or thousands without
  92. one to instructions that take one cycle.
  93.  
  94.   Further gains can be made by making your max and min values exactly 
  95. fit the bounds of the bitmap and the video screen or window. 
  96.